import java.util.ArrayDeque;
import java.util.Deque;

/**
* @description: 856. 括号的分数
* @author hewei
* @date 2022/9/8 21:08
* @version 1.0
*/

public class ScoreOfParentheses {

    public int scoreOfParentheses(String s) {
        if (s.length() == 2) return 1;
        int count = 1;
        for (int i = 1; i < s.length() - 1; i++) {
            char c = s.charAt(i);
            if (c == '(') ++count;
            else --count;
            if (count == 0) return scoreOfParentheses(s.substring(0, i + 1)) + scoreOfParentheses(s.substring(i + 1));
        }
        return 2 * scoreOfParentheses(s.substring(1, s.length() - 1));
    }

    public int scoreOfParentheses1(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(0);
            } else {
                stack.push(Math.max(1, stack.pop() * 2) + stack.pop());
            }
        }
        return stack.pop();
    }
}
